SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Generalized minimum-distance decoding</title>

</head>

Generalized minimum-distance decoding

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Coding_theory" title="Coding theory">coding theory</a>, generalized minimum-distance (GMD) decoding provides an efficient <a href="Algorithm" title="Algorithm">algorithm</a> for decoding <a href="Concatenated_code" class="mw-redirect" title="Concatenated code">concatenated codes</a>, which is based on using an <a href="Error" title="Error">errors</a>-and-<a href="Erasure_code" title="Erasure code">erasures</a> decoder for the <a href="Outer_code" class="mw-redirect" title="Outer code">outer code</a>.

A <a href="Concatenated_error_correction_code#Decoding_concatenated_codes" title="Concatenated error correction code">naive decoding algorithm</a> for concatenated codes can not be an optimal way of decoding because it does not take into account the information that <a href="Maximum_likelihood_decoding" class="mw-redirect" title="Maximum likelihood decoding">maximum likelihood decoding</a> (MLD) gives. In other words, in the naive algorithm, inner received <a href="Code_word_(communication)" title="Code word (communication)">codewords</a> are treated the same regardless of the difference between their <a href="Hamming_distance" title="Hamming distance">hamming distances</a>. Intuitively, the outer decoder should place higher confidence in symbols whose inner <a href="Code" title="Code">encodings</a> are close to the received word. <a href="David_Forney" class="mw-redirect" title="David Forney">David Forney</a> in 1966 devised a better algorithm called generalized minimum distance (GMD) decoding which makes use of those information better. This method is achieved by measuring confidence of each received codeword, and erasing symbols whose confidence is below a desired value. And GMD decoding algorithm was one of the first examples of <a href="Soft-decision_decoder" title="Soft-decision decoder">soft-decision decoders</a>. We will present three versions of the GMD decoding algorithm. The first two will be <a href="Randomized_algorithm" title="Randomized algorithm">randomized algorithms</a> while the last one will be a <a href="Deterministic_algorithm" title="Deterministic algorithm">deterministic algorithm</a>.

<div class="mw-heading mw-heading2"><h2 id="Setup">Setup</h2></div>

<ul><li><a href="Hamming_distance" title="Hamming distance">Hamming distance</a> : Given two <a href="Euclidean_vector" title="Euclidean vector">vectors</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u,v\in \Sigma ^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u,v\in \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./faee1f5bc0e07a6ad077e16b9c886fa920ff5eef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.228ex; height:2.676ex;" alt="{\displaystyle u,v\in \Sigma ^{n}}" loading="lazy"> the Hamming distance between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</math><img src="./c3e6bb763d22c20916ed4f0bb6bd49d7470cffd8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle u}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">, denoted by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta (u,v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta (u,v)}</annotation>

</semantics>

</math><img src="./1297a547da9c86b641cd297d85796c8573d586e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.236ex; height:2.843ex;" alt="{\displaystyle \Delta (u,v)}" loading="lazy">, is defined to be the number of positions in which <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle u}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

<li>Minimum distance: Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C\subseteq \Sigma ^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C\subseteq \Sigma ^{n}}</annotation>

</semantics>

</math><img src="./0b38b44f13a27edcf3055714dea592113042ad3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.761ex; height:2.509ex;" alt="{\displaystyle C\subseteq \Sigma ^{n}}" loading="lazy"> be a <a href="Code" title="Code">code</a>. The minimum distance of code <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is defined to be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=\min \Delta (c_{1},c_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=\min \Delta (c_{1},c_{2})}</annotation>

</semantics>

</math><img src="./cacfd24338175bbc5d0137748c079768e7bc6ad4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.478ex; height:2.843ex;" alt="{\displaystyle d=\min \Delta (c_{1},c_{2})}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{1}\neq c_{2}\in C}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{1}\neq c_{2}\in C}</annotation>

</semantics>

</math><img src="./9add2a533ca53cf46d4442fb8a76c70eb98c9639.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.828ex; height:2.676ex;" alt="{\displaystyle c_{1}\neq c_{2}\in C}" loading="lazy"></li>

<li>Code concatenation: Given <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=(m_{1},\cdots ,m_{K})\in [Q]^{K}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=(m_{1},\cdots ,m_{K})\in [Q]^{K}}</annotation>

</semantics>

</math><img src="./beebc5268b4378e4c3b142da1d861b22f98f34ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.62ex; height:3.176ex;" alt="{\displaystyle m=(m_{1},\cdots ,m_{K})\in [Q]^{K}}" loading="lazy">, consider two codes which we call outer code and inner code</li></ul>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{\text{out}}=[Q]^{K}\to [Q]^{N},\qquad C_{\text{in}}:[q]^{k}\to [q]^{n},}</annotation>

</semantics>

</math><img src="./7b432223854f52245cf6ae62bd998f8a6daea11f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.807ex; height:3.176ex;" alt="{\displaystyle C_{\text{out}}=[Q]^{K}\to [Q]^{N},\qquad C_{\text{in}}:[q]^{k}\to [q]^{n},}" loading="lazy"></dd></dl></dd>

<dd>and their distances are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy">. A concatenated code can be achieved by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\text{out}}\circ C_{\text{in}}(m)=(C_{\text{in}}(C_{\text{out}}(m)_{1}),\ldots ,C_{\text{in}}(C_{\text{out}}(m)_{N}))}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{\text{out}}\circ C_{\text{in}}(m)=(C_{\text{in}}(C_{\text{out}}(m)_{1}),\ldots ,C_{\text{in}}(C_{\text{out}}(m)_{N}))}</annotation>

</semantics>

</math><img src="./7b681e17679a831ba44a7aa85962217e8592b32b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:52.799ex; height:2.843ex;" alt="{\displaystyle C_{\text{out}}\circ C_{\text{in}}(m)=(C_{\text{in}}(C_{\text{out}}(m)_{1}),\ldots ,C_{\text{in}}(C_{\text{out}}(m)_{N}))}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\text{out}}(m)=((C_{\text{out}}(m)_{1},\ldots ,(m)_{N})).}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{\text{out}}(m)=((C_{\text{out}}(m)_{1},\ldots ,(m)_{N})).}</annotation>

</semantics>

</math><img src="./f20008bb533f089a55fb8924e77843e49217c42c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:35.376ex; height:2.843ex;" alt="{\displaystyle C_{\text{out}}(m)=((C_{\text{out}}(m)_{1},\ldots ,(m)_{N})).}" loading="lazy"> Finally we will take <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\text{out}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{\text{out}}}</annotation>

</semantics>

</math><img src="./4bfc32bfd34c08ae62543c3bffd1074eef0cea17.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.27ex; height:2.509ex;" alt="{\displaystyle C_{\text{out}}}" loading="lazy"> to be <a href="Reed_Solomon" class="mw-redirect" title="Reed Solomon">RS code</a>, which has an errors and erasure decoder, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K=O(\log N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K=O(\log N)}</annotation>

</semantics>

</math><img src="./5a32dd4bbb6bfc91ff48fcccdbc66e87a4ec3d32.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.169ex; height:2.843ex;" alt="{\displaystyle K=O(\log N)}" loading="lazy">, which in turn implies that MLD on the inner code will be polynomial in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> time.</dd></dl>

<ul><li>Maximum likelihood decoding (MLD): MLD is a decoding method for error correcting codes, which outputs the codeword closest to the received word in Hamming distance. The MLD function denoted by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D_{MLD}:\Sigma ^{n}\to C}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D_{MLD}:\Sigma ^{n}\to C}</annotation>

</semantics>

</math><img src="./f88b2f82de107293f08b05fece368f5125c9fbfd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.577ex; height:2.676ex;" alt="{\displaystyle D_{MLD}:\Sigma ^{n}\to C}" loading="lazy"> is defined as follows. For every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in \Sigma ^{n},D_{MLD}(y)=\arg \min _{c\in C}\Delta (c,y)}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in \Sigma ^{n},D_{MLD}(y)=\arg \min _{c\in C}\Delta (c,y)}</annotation>

</semantics>

</math><img src="./a344f0634581d4acdc8f8bfc7136fee6136662e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:35.181ex; height:4.176ex;" alt="{\displaystyle y\in \Sigma ^{n},D_{MLD}(y)=\arg \min _{c\in C}\Delta (c,y)}" loading="lazy">.</li>

<li><a href="Probability_density_function" title="Probability density function">Probability density function</a> : A <a href="Probability_distribution" title="Probability distribution">probability distribution</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pr }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr }</annotation>

</semantics>

</math><img src="./50be466e52dac236652eedbbfb5660e570f2a5e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.494ex; height:2.176ex;" alt="{\displaystyle \Pr }" loading="lazy"> on a sample space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> is a mapping from events of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> to <a href="Real_number" title="Real number">real numbers</a> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pr[A]\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[A]\geq 0}</annotation>

</semantics>

</math><img src="./6288934954082f698bf416ec2e02012076bb8201.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.792ex; height:2.843ex;" alt="{\displaystyle \Pr[A]\geq 0}" loading="lazy"> for any event <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A,\Pr[S]=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A,\Pr[S]=1}</annotation>

</semantics>

</math><img src="./e0d0a40d7ab301d922bb23a4aab02f35c561b0bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.325ex; height:2.843ex;" alt="{\displaystyle A,\Pr[S]=1}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pr[A\cup B]=\Pr[A]+\Pr[B]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[A\cup B]=\Pr[A]+\Pr[B]}</annotation>

</semantics>

</math><img src="./e6ee60e15bc1b75b8cfc8aab87dc4b4782ea148a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.9ex; height:2.843ex;" alt="{\displaystyle \Pr[A\cup B]=\Pr[A]+\Pr[B]}" loading="lazy"> for any two mutually exclusive events <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></li>

<li><a href="Expected_value" title="Expected value">Expected value</a>: The expected value of a <a href="Discrete_random_variable" class="mw-redirect" title="Discrete random variable">discrete random variable</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> is</li></ul>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} [X]=\sum _{x}\Pr[X=x].}</annotation>

</semantics>

</math><img src="./2b00b4c96e658352175021ec4aad62193c660043.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:22.508ex; height:5.509ex;" alt="{\displaystyle \mathbb {E} [X]=\sum _{x}\Pr[X=x].}" loading="lazy"></dd></dl></dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Randomized_algorithm">Randomized algorithm</h2></div>

Consider the received word <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}</annotation>

</semantics>

</math><img src="./2ea19682e7b48cc1eed64ce84618339e1cc1dbc3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.645ex; height:3.176ex;" alt="{\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}" loading="lazy"> which was corrupted by a <a href="Noisy_channel" class="mw-redirect" title="Noisy channel">noisy channel</a>. The following is the algorithm description for the general case. In this algorithm, we can decode y by just declaring an erasure at every bad position and running the errors and erasure decoding algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\text{out}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{\text{out}}}</annotation>

</semantics>

Randomized_Decoder

Given : <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} =(y_{1},\dots ,y_{N})\in [q^{n}]^{N}}">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} =(y_{1},\dots ,y_{N})\in [q^{n}]^{N}}</annotation>

</semantics>

</math><img src="./6ffdf051ef56d3a7862b02ebf301a89119320f1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.645ex; height:3.176ex;" alt="{\displaystyle \mathbf {y} =(y_{1},\dots ,y_{N})\in [q^{n}]^{N}}" loading="lazy">.

<ol><li>For every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq N}</annotation>

</semantics>

</math><img src="./67264d2c71d18cea43cbd2507d651d22f67c6171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.225ex; height:2.343ex;" alt="{\displaystyle 1\leq i\leq N}" loading="lazy">, compute <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}">

</mrow>

</msubsup>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{\tfrac {d}{2}})}</annotation>

</semantics>

</math><img src="./bbac081f90470388f92ce7a18e4f5cf4dc952b39.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:27.49ex; height:3.676ex;" alt="{\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{\tfrac {d}{2}})}" loading="lazy">.</li>

<li>For every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq N}</annotation>

</semantics>

</math><img src="./67264d2c71d18cea43cbd2507d651d22f67c6171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.225ex; height:2.343ex;" alt="{\displaystyle 1\leq i\leq N}" loading="lazy">, repeat : With probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\omega _{i} \over d}">

<mfrac>

<msub>

</mrow>

</msub>

</mstyle>

</mfrac>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\omega _{i} \over d}</annotation>

</semantics>

</math><img src="./4b9af97ae643519b7d03908eb2bf1c2c1f480041.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:4.244ex; height:5.343ex;" alt="{\displaystyle 2\omega _{i} \over d}" loading="lazy">, set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}''\leftarrow ?,}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}''\leftarrow ?,}</annotation>

</semantics>

</math><img src="./c02099637240d09bee0a3924cf0769e4e9e5373d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.011ex; height:2.843ex;" alt="{\displaystyle y_{i}''\leftarrow ?,}" loading="lazy"> otherwise set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}''=y_{i}'}">

</mrow>

</msubsup>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}''=y_{i}'}</annotation>

</semantics>

</math><img src="./dff41242718efc1c42b3fb3d99108670fdcd1b6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.335ex; height:2.843ex;" alt="{\displaystyle y_{i}''=y_{i}'}" loading="lazy">.</li>

<li>Run errors and erasure algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\text{out}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{\text{out}}}</annotation>

</semantics>

</math><img src="./4bfc32bfd34c08ae62543c3bffd1074eef0cea17.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.27ex; height:2.509ex;" alt="{\displaystyle C_{\text{out}}}" loading="lazy"> on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}">

<msup>

</mrow>

</msup>

</mrow>

</msubsup>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}</annotation>

</semantics>

Theorem 1. Let y be a received word such that there exists a <a href="Code_word_(communication)" title="Code word (communication)">codeword</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {c} =(c_{1},\cdots ,c_{N})\in C_{\text{out}}\circ {C_{\text{in}}}\subseteq [q^{n}]^{N}}">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {c} =(c_{1},\cdots ,c_{N})\in C_{\text{out}}\circ {C_{\text{in}}}\subseteq [q^{n}]^{N}}</annotation>

</semantics>

</math><img src="./e490424b04ef05f869fdb5714b6a81a3ee4371a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.985ex; height:3.176ex;" alt="{\displaystyle \mathbf {c} =(c_{1},\cdots ,c_{N})\in C_{\text{out}}\circ {C_{\text{in}}}\subseteq [q^{n}]^{N}}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta (\mathbf {c} ,\mathbf {y} )<{\tfrac {Dd}{2}}}">

</mrow>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta (\mathbf {c} ,\mathbf {y} )<{\tfrac {Dd}{2}}}</annotation>

</semantics>

</math><img src="./28ada74b550fb78d1196b0e5d9e90b826e668c83.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:13.533ex; height:3.676ex;" alt="{\displaystyle \Delta (\mathbf {c} ,\mathbf {y} )<{\tfrac {Dd}{2}}}" loading="lazy">. Then the deterministic GMD algorithm outputs <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {c} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {c} }</annotation>

</semantics>

Note that a <a href="Concatenated_codes" class="mw-redirect" title="Concatenated codes">naive decoding algorithm for concatenated codes</a> can correct up to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {Dd}{4}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {Dd}{4}}}</annotation>

</semantics>

</math><img src="./c0b2d4cde4b68d7c58ce89d2b3c4ffb7eca19843.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:3.057ex; height:3.676ex;" alt="{\displaystyle {\tfrac {Dd}{4}}}" loading="lazy"> errors.

<dl><dd>Lemma 1. Let the assumption in Theorem 1 hold. And if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} ''}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} ''}</annotation>

</semantics>

</math><img src="./8adc93de7348e26508eee01021183078649b200b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.548ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} ''}" loading="lazy"> has <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e'}</annotation>

</semantics>

</math><img src="./06c198f6710d781baaf94653df305a4881380033.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.768ex; height:2.509ex;" alt="{\displaystyle e'}" loading="lazy"> errors and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s'}</annotation>

</semantics>

</math><img src="./5136680c63706cfd17ceddb4acddbfdd0ba5ef2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.775ex; height:2.509ex;" alt="{\displaystyle s'}" loading="lazy"> erasures (when compared with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {c} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {c} }</annotation>

</semantics>

</math><img src="./8798d172f59e21f2ce193a3118d4063d19353ded.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.188ex; height:1.676ex;" alt="{\displaystyle \mathbf {c} }" loading="lazy">) after Step 1, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} [2e'+s']<D.}">

</mrow>

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} [2e'+s']<D.}</annotation>

</semantics>

</math><img src="./504bbe8ae8fbbd701e22fdc916b9da981a3d91c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.06ex; height:3.009ex;" alt="{\displaystyle \mathbb {E} [2e'+s']<D.}" loading="lazy"></dd></dl>

Remark. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2e'+s'<D}">

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2e'+s'<D}</annotation>

</semantics>

</math><img src="./3ce26b24a97db6892ae8c861d528272955075777.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.569ex; height:2.676ex;" alt="{\displaystyle 2e'+s'<D}" loading="lazy">, then the algorithm in Step 2 will output <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {c} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {c} }</annotation>

</semantics>

</math><img src="./8798d172f59e21f2ce193a3118d4063d19353ded.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.188ex; height:1.676ex;" alt="{\displaystyle \mathbf {c} }" loading="lazy">. The lemma above says that in expectation, this is indeed the case. Note that this is not enough to prove Theorem 1, but can be crucial in developing future variations of the algorithm.

Proof of lemma 1. For every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq N,}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq N,}</annotation>

</semantics>

</math><img src="./f2182bf81dc3092abccdb59006d400ead1236586.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.872ex; height:2.509ex;" alt="{\displaystyle 1\leq i\leq N,}" loading="lazy"> define <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e_{i}=\Delta (y_{i},c_{i}).}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e_{i}=\Delta (y_{i},c_{i}).}</annotation>

</semantics>

</math><img src="./2fd2f570474ed28b8d3f18eaa9b660cb4a842fab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.153ex; height:2.843ex;" alt="{\displaystyle e_{i}=\Delta (y_{i},c_{i}).}" loading="lazy"> This implies that

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{N}e_{i}<{\frac {Dd}{2}}\qquad \qquad (1)}</annotation>

</semantics>

</math>

Next for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq N}</annotation>

</semantics>

</math><img src="./67264d2c71d18cea43cbd2507d651d22f67c6171.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.225ex; height:2.343ex;" alt="{\displaystyle 1\leq i\leq N}" loading="lazy">, we define two <a href="Indicator_variable" class="mw-redirect" title="Indicator variable">indicator variables</a>:

<mtr>

<mtd>

</mrow>

</mrow>

</msubsup>

</mrow>

</mtd>

<mtd>

</mrow>

</msubsup>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</msubsup>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}X{_{i}^{?}}=1&\Leftrightarrow y_{i}''=?\\X{_{i}^{e}}=1&\Leftrightarrow C_{\text{in}}(y_{i}'')\neq c_{i}\ {\text{and}}\ y_{i}''\neq ?\end{aligned}}}</annotation>

</semantics>

</math>

We claim that we are done if we can show that for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq N}</annotation>

</semantics>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} \left[2X{_{i}^{e}+X{_{i}^{?}}}\right]\leqslant {2e_{i} \over d}\qquad \qquad (2)}</annotation>

</semantics>

</math>

Clearly, by definition

<msup>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

</msubsup>

</mrow>

<msup>

</msup>

</mrow>

</munder>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e'=\sum _{i}X_{i}^{e}\quad {\text{and}}\quad s'=\sum _{i}X_{i}^{?}.}</annotation>

</semantics>

</math>

Further, by the <a href="Linear" class="mw-redirect" title="Linear">linearity</a> of expectation, we get

</mrow>

<msup>

</msup>

<msup>

</msup>

<mfrac>

</mfrac>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} [2e'+s']\leqslant {\frac {2}{d}}\sum _{i}e_{i}<D.}</annotation>

</semantics>

</math>

To prove (2) we consider two cases: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">-th block is correctly decoded (Case 1), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

Case 1: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (c_{i}=C_{\text{in}}(y_{i}'))}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (c_{i}=C_{\text{in}}(y_{i}'))}</annotation>

</semantics>

</math><img src="./cf37e739cb066382e81a2a1da19fc97220b8ee3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.728ex; height:3.009ex;" alt="{\displaystyle (c_{i}=C_{\text{in}}(y_{i}'))}" loading="lazy">

Note that if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}''=?}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}''=?}</annotation>

</semantics>

</math><img src="./1077d2071e7ee6f7a1b5415b7d0d1c00b0a83b9e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.848ex; height:2.843ex;" alt="{\displaystyle y_{i}''=?}" loading="lazy"> then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{i}^{e}=0}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{i}^{e}=0}</annotation>

</semantics>

</math><img src="./c0a7ba422133b7e60f2ccbddff588eb8fa975a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.256ex; height:2.843ex;" alt="{\displaystyle X_{i}^{e}=0}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pr[y_{i}''=?]={\tfrac {2\omega _{i}}{d}}}">

</mrow>

</msubsup>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[y_{i}''=?]={\tfrac {2\omega _{i}}{d}}}</annotation>

</semantics>

</math><img src="./6fb95b0b12a259213e11afbab1653625b6a546dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:16.04ex; height:4.009ex;" alt="{\displaystyle \Pr[y_{i}''=?]={\tfrac {2\omega _{i}}{d}}}" loading="lazy"> implies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} [X_{i}^{?}]=\Pr[X_{i}^{?}=1]={\tfrac {2\omega _{i}}{d}},}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} [X_{i}^{?}]=\Pr[X_{i}^{?}=1]={\tfrac {2\omega _{i}}{d}},}</annotation>

</semantics>

</math><img src="./7b8ba82f10513d556e247f949524456c52c27f6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:27.052ex; height:4.009ex;" alt="{\displaystyle \mathbb {E} [X_{i}^{?}]=\Pr[X_{i}^{?}=1]={\tfrac {2\omega _{i}}{d}},}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=0}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=0}</annotation>

</semantics>

</math><img src="./2140e574d338b5c0a6d539e5f7e93d8ec5d685df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:24.243ex; height:3.009ex;" alt="{\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=0}" loading="lazy">.

Further, by definition we have

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega _{i}=\min \left(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{\tfrac {d}{2}}\right)\leqslant \Delta (C_{\text{in}}(y_{i}'),y_{i})=\Delta (c_{i},y_{i})=e_{i}}</annotation>

</semantics>

</math>

Case 2: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (c_{i}\neq C_{\text{in}}(y_{i}'))}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (c_{i}\neq C_{\text{in}}(y_{i}'))}</annotation>

</semantics>

</math><img src="./767562da6d894cb70ed16f6f6030c842a84d36c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.728ex; height:3.009ex;" alt="{\displaystyle (c_{i}\neq C_{\text{in}}(y_{i}'))}" loading="lazy">

In this case, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} [X_{i}^{?}]={\tfrac {2\omega _{i}}{d}}}">

</mrow>

</mrow>

</mrow>

</msubsup>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} [X_{i}^{?}]={\tfrac {2\omega _{i}}{d}}}</annotation>

</semantics>

</math><img src="./ab481e0b4b4df0089746e87cb2d881505a0e890b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:12.253ex; height:4.009ex;" alt="{\displaystyle \mathbb {E} [X_{i}^{?}]={\tfrac {2\omega _{i}}{d}}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=1-{\tfrac {2\omega _{i}}{d}}.}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=1-{\tfrac {2\omega _{i}}{d}}.}</annotation>

</semantics>

</math><img src="./618724c3e59f7524419397d248965e589155e8d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:31.036ex; height:4.009ex;" alt="{\displaystyle \mathbb {E} [X_{i}^{e}]=\Pr[X_{i}^{e}=1]=1-{\tfrac {2\omega _{i}}{d}}.}" loading="lazy">

Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}\neq C_{\text{in}}(y_{i}'),e_{i}+\omega _{i}\geqslant d}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}\neq C_{\text{in}}(y_{i}'),e_{i}+\omega _{i}\geqslant d}</annotation>

</semantics>

</math><img src="./f30320c7412af6a366f6e861218dc4f5b739b670.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:24.236ex; height:3.009ex;" alt="{\displaystyle c_{i}\neq C_{\text{in}}(y_{i}'),e_{i}+\omega _{i}\geqslant d}" loading="lazy">. This follows <a rel="nofollow" class="external text" href="http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures/lect28.pdf">another case analysis</a> when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\omega _{i}=\Delta (C_{\text{in}}(y_{i}'),y_{i})<{\tfrac {d}{2}})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\omega _{i}=\Delta (C_{\text{in}}(y_{i}'),y_{i})<{\tfrac {d}{2}})}</annotation>

</semantics>

</math><img src="./458e56e8e3ce545e7d417487ec60470cee9664d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:25.679ex; height:3.676ex;" alt="{\displaystyle (\omega _{i}=\Delta (C_{\text{in}}(y_{i}'),y_{i})<{\tfrac {d}{2}})}" loading="lazy"> or not.

Finally, this implies

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} [2X_{i}^{e}+X_{i}^{?}]=2-{2\omega _{i} \over d}\leq {2e_{i} \over d}.}</annotation>

</semantics>

</math>

In the following sections, we will finally show that the deterministic version of the algorithm above can do unique decoding of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\text{out}}\circ C_{\text{in}}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{\text{out}}\circ C_{\text{in}}}</annotation>

</semantics>

</math><img src="./f370c8eba7623cfa77551962999e94850fe20200.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.73ex; height:2.509ex;" alt="{\displaystyle C_{\text{out}}\circ C_{\text{in}}}" loading="lazy"> up to half its design distance.

<div class="mw-heading mw-heading2"><h2 id="Modified_randomized_algorithm">Modified randomized algorithm</h2></div>

Note that, in the previous version of the GMD algorithm in step "3", we do not really need to use "fresh" <a href="Randomness" title="Randomness">randomness</a> for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">. Now we come up with another randomized version of the GMD algorithm that uses the same randomness for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

Modified_Randomized_Decoder

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta \in [0,1]}</annotation>

</semantics>

</math><img src="./fead1e7dceab4be5ab2e91f5108144722daa8c36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.584ex; height:2.843ex;" alt="{\displaystyle \theta \in [0,1]}" loading="lazy"> at random. Then every for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq N}</annotation>

</semantics>

</mrow>

</msubsup>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}</annotation>

</semantics>

<li>Compute <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{d \over 2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{d \over 2})}</annotation>

</semantics>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta <{\tfrac {2\omega _{i}}{d}}}</annotation>

</semantics>

</math><img src="./3969e440695e5fa729879a6be15891a2017436ad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:7.494ex; height:4.009ex;" alt="{\displaystyle \theta <{\tfrac {2\omega _{i}}{d}}}" loading="lazy">, set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}''\leftarrow ?,}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}''\leftarrow ?,}</annotation>

</semantics>

</mrow>

</msubsup>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}''=y_{i}'}</annotation>

</semantics>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{\text{out}}}</annotation>

</semantics>

</math><img src="./4bfc32bfd34c08ae62543c3bffd1074eef0cea17.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.27ex; height:2.509ex;" alt="{\displaystyle C_{\text{out}}}" loading="lazy"> on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}">

<msup>

</mrow>

</msup>

</mrow>

</msubsup>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}</annotation>

</semantics>

For the proof of <a href="Lemma_(mathematics)" title="Lemma (mathematics)">Lemma 1</a>, we only use the randomness to show that

</mrow>

</msubsup>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[y_{i}''=?]={2\omega _{i} \over d}.}</annotation>

</semantics>

</math>

In this version of the GMD algorithm, we note that

</mrow>

</msubsup>

<mrow>

<mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mrow>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[y_{i}''=?]=\Pr \left[\theta \in \left[0,{\tfrac {2\omega _{i}}{d}}\right]\right]={\tfrac {2\omega _{i}}{d}}.}</annotation>

</semantics>

</math>

The second <a href="Equality_(mathematics)" title="Equality (mathematics)">equality</a> above follows from the choice of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy">. The proof of Lemma 1 can be also used to show <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {E} [2e'+s']<D}">

</mrow>

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {E} [2e'+s']<D}</annotation>

</semantics>

</math><img src="./419492596494760f9ea47ab39b9206dfbe33679c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.413ex; height:3.009ex;" alt="{\displaystyle \mathbb {E} [2e'+s']<D}" loading="lazy"> for version2 of GMD. In the next section, we will see how to get a deterministic version of the GMD algorithm by choosing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> from a polynomially sized set as opposed to the current infinite set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0,1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [0,1]}</annotation>

</semantics>

</math><img src="./738f7d23bb2d9642bab520020873cccbef49768d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.653ex; height:2.843ex;" alt="{\displaystyle [0,1]}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Deterministic_algorithm">Deterministic algorithm</h2></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q=\{0,1\}\cup \{{2\omega _{1} \over d},\ldots ,{2\omega _{N} \over d}\}}">

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q=\{0,1\}\cup \{{2\omega _{1} \over d},\ldots ,{2\omega _{N} \over d}\}}</annotation>

</semantics>

</math><img src="./875a59a4d70a722434b826cc2229ddcff095e094.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:30.341ex; height:5.343ex;" alt="{\displaystyle Q=\{0,1\}\cup \{{2\omega _{1} \over d},\ldots ,{2\omega _{N} \over d}\}}" loading="lazy">. Since for each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i,\omega _{i}=\min(\Delta (\mathbf {y_{i}'} ,\mathbf {y_{i}} ),{d \over 2})}">

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i,\omega _{i}=\min(\Delta (\mathbf {y_{i}'} ,\mathbf {y_{i}} ),{d \over 2})}</annotation>

</semantics>

</math><img src="./0cfba0fb7d5c6023a5a59f0f01ab06aebe222636.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:25.066ex; height:5.343ex;" alt="{\displaystyle i,\omega _{i}=\min(\Delta (\mathbf {y_{i}'} ,\mathbf {y_{i}} ),{d \over 2})}" loading="lazy">, we have

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q=\{0,1\}\cup \{q_{1},\ldots ,q_{m}\}}</annotation>

</semantics>

</math>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{1}<\cdots <q_{m}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{1}<\cdots <q_{m}}</annotation>

</semantics>

</math><img src="./e8e100d069d319e937d27cd7a7635f12c484927c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.724ex; height:2.176ex;" alt="{\displaystyle q_{1}<\cdots <q_{m}}" loading="lazy"> for some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\leq \left\lfloor {\frac {d}{2}}\right\rfloor }">

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\leq \left\lfloor {\frac {d}{2}}\right\rfloor }</annotation>

</semantics>

</math><img src="./29ce9f783d7cff5de6494b96166bfcb96473b822.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:9.901ex; height:6.176ex;" alt="{\displaystyle m\leq \left\lfloor {\frac {d}{2}}\right\rfloor }" loading="lazy">. Note that for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta \in [q_{i},q_{i+1}]}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta \in [q_{i},q_{i+1}]}</annotation>

</semantics>

</math><img src="./817aa31ed3131d36737531dacc009f27c8e20e1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.033ex; height:2.843ex;" alt="{\displaystyle \theta \in [q_{i},q_{i+1}]}" loading="lazy">, the step 1 of the second version of randomized algorithm outputs the same <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} ''.}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} ''.}</annotation>

</semantics>

</math><img src="./1df678482ad7811af8ce4bf40372093fea8760ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.195ex; height:2.843ex;" alt="{\displaystyle \mathbf {y} ''.}" loading="lazy">. Thus, we need to consider all possible value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta \in Q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta \in Q}</annotation>

</semantics>

</math><img src="./c058654984a61e907d02302eeaf15822d465c321.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.769ex; height:2.509ex;" alt="{\displaystyle \theta \in Q}" loading="lazy">. This gives the deterministic algorithm below.

Deterministic_Decoder

Given : <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} =(y_{1},\ldots ,y_{N})\in [q^{n}]^{N}}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta \in Q}</annotation>

</semantics>

<ol><li>Compute <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}">

</mrow>

</msubsup>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}</annotation>

</semantics>

</math><img src="./4fee69c208c1793d8ceba2e225bfeee8b7580062.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.42ex; height:3.009ex;" alt="{\displaystyle y_{i}'=MLD_{C_{\text{in}}}(y_{i})}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq N}</annotation>

</semantics>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{d \over 2})}</annotation>

</semantics>

</math><img src="./4d630a51cf6b028dfdaab6ca2d8db16115479105.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:27.846ex; height:5.343ex;" alt="{\displaystyle \omega _{i}=\min(\Delta (C_{\text{in}}(y_{i}'),y_{i}),{d \over 2})}" loading="lazy"> for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i\leq N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq N}</annotation>

</semantics>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta <{2\omega _{i} \over d}}</annotation>

</semantics>

</math><img src="./e25a33cf184ac0480f0ac00ae9a7ea2536093c71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:8.433ex; height:5.343ex;" alt="{\displaystyle \theta <{2\omega _{i} \over d}}" loading="lazy">, set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}''\leftarrow ?,}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}''\leftarrow ?,}</annotation>

</semantics>

</mrow>

</msubsup>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}''=y_{i}'}</annotation>

</semantics>

<li>Run errors-and-erasures algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\text{out}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{\text{out}}}</annotation>

</semantics>

</math><img src="./4bfc32bfd34c08ae62543c3bffd1074eef0cea17.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.27ex; height:2.509ex;" alt="{\displaystyle C_{\text{out}}}" loading="lazy"> on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}">

<msup>

</mrow>

</msup>

</mrow>

</msubsup>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}</annotation>

</semantics>

</math><img src="./9f8c5563d26dd791d02cba7aea16a31a7d197109.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.762ex; height:3.176ex;" alt="{\displaystyle \mathbf {y} ''=(y_{1}'',\ldots ,y_{N}'')}" loading="lazy">. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{\theta }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{\theta }}</annotation>

</semantics>

</math><img src="./14a92159d9634f6420c19c90b66e068a07ec2f84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.01ex; height:2.009ex;" alt="{\displaystyle c_{\theta }}" loading="lazy"> be the codeword in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{\text{out}}\circ C_{\text{in}}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{\text{out}}\circ C_{\text{in}}}</annotation>

</semantics>

<li>Among all the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{\theta }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{\theta }}</annotation>

</semantics>

</math><img src="./14a92159d9634f6420c19c90b66e068a07ec2f84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.01ex; height:2.009ex;" alt="{\displaystyle c_{\theta }}" loading="lazy"> output in 4, output the one closest to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {y} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {y} }</annotation>

</semantics>

</math><img src="./bb25a040b592282dc2a254c3117e792c3c81161f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.411ex; height:2.009ex;" alt="{\displaystyle \mathbf {y} }" loading="lazy"></li></ol>

Every loop of 1~4 can be run in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a>, the algorithm above can also be computed in polynomial time. Specifically, each call to an errors and erasures decoder of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle <dD/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle <dD/2}</annotation>

</semantics>

</math><img src="./f05c63213faef2234245b2575b1f0a3747237261.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.918ex; height:2.843ex;" alt="{\displaystyle <dD/2}" loading="lazy"> errors takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(d)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(d)}</annotation>

</semantics>

</math><img src="./6e323ee705f0664132bf796619cf0e2b36a1c396.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.798ex; height:2.843ex;" alt="{\displaystyle O(d)}" loading="lazy"> time. Finally, the runtime of the algorithm above is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(NQn^{O(1)}+NT_{\text{out}})}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(NQn^{O(1)}+NT_{\text{out}})}</annotation>

</semantics>

</math><img src="./1bcd7611120508d08c9d4043604415b9a0695287.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.336ex; height:3.343ex;" alt="{\displaystyle O(NQn^{O(1)}+NT_{\text{out}})}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{out}}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{\text{out}}}</annotation>

</semantics>

</math><img src="./4837d1878aba04986fa8997aff3b23e25275dbd6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.965ex; height:2.509ex;" alt="{\displaystyle T_{\text{out}}}" loading="lazy"> is the running time of the outer errors and erasures decoder.

<ul><li><a href="Concatenated_code" class="mw-redirect" title="Concatenated code">Concatenated codes</a></li>

<li><a href="Reed_Solomon" class="mw-redirect" title="Reed Solomon">Reed Solomon error correction</a></li>

<li><a href="Berlekamp%E2%80%93Welch_algorithm" title="Berlekamp–Welch algorithm">Welch Berlekamp algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.cse.buffalo.edu/~atri/courses/coding-theory/lectures">University at Buffalo Lecture Notes on Coding Theory – Atri Rudra</a></li>

<li><a rel="nofollow" class="external text" href="http://people.csail.mit.edu/madhu/FT01">MIT Lecture Notes on Essential Coding Theory – Madhu Sudan</a></li>

<li><a rel="nofollow" class="external text" href="http://www.cs.washington.edu/education/courses/cse533/06au">University of Washington – Venkatesan Guruswami</a></li>

<li>G. David Forney. Generalized Minimum Distance decoding. IEEE Transactions on Information Theory, 12:125–131, 1966</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2023-10-24" href="https://en.wikipedia.org/wiki/?title=Generalized_minimum-distance_decoding&oldid=1181598299">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>